/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30



␈↓ α∧␈↓CS206␈↓ ¬TFINAL EXAMINATION␈↓ 
lFALL 1976 

␈↓ α∧␈↓␈↓ αTThis␈α
examination␈α
is␈α
open␈α
book␈α
and␈α∞notes.␈α
 Write␈α
LISP␈α
functions␈α
as␈α
follows␈α∞except␈α
where
␈↓ α∧␈↓something else is requested.  Either notation may be used.

␈↓ α∧␈↓1. ␈↓↓noccurl[x,u]␈↓ is the number of occurrences of the S-expression ␈↓↓x␈↓ in the list ␈↓↓u␈↓ (at the top level).

␈↓ α∧␈↓Example: ␈↓↓noccurl[␈↓(A) , ((A) B ((A)) (A) A)] = 2.

␈↓ α∧␈↓2.␈α∀␈↓↓noccurs[x,y]␈↓␈α∀is␈α∀the␈α∀number␈α∀of␈α∀occurrences␈α∪of␈α∀the␈α∀S-expression␈α∀␈↓↓x␈↓␈α∀in␈α∀the␈α∀S-expression␈α∪␈↓↓y␈↓
␈↓ α∧␈↓(anywhere).

␈↓ α∧␈↓Example: ␈↓↓noccurs␈↓[(A) , ((A) B ((A)) (A) A)] = 4.

␈↓ α∧␈↓3. ␈↓↓samefringe[x,y]␈↓ is true if ␈↓↓x␈↓ and ␈↓↓y␈↓ have the same atoms in the same order.  Thus

␈↓ α∧␈↓␈↓ αT␈↓↓samefringe[␈↓((A.B).C) , (A.(B.C))].

␈↓ α∧␈↓Write ␈↓↓samefringe␈↓ without flattening the lists ␈↓↓x␈↓ and ␈↓↓y.␈↓

␈↓ α∧␈↓4. We define

␈↓ α∧␈↓␈↓ αT␈↓↓prina[e,l] ← ␈↓αif␈↓↓ ␈↓αa␈↓↓t e ␈↓αthen␈↓↓ e . l ␈↓αelse␈↓↓ ␈↓LP . ␈↓↓prina[␈↓αa␈↓↓ e, ␈↓DOT␈↓↓ . prina[␈↓αd␈↓↓ e, ␈↓RP␈↓↓ . l]]␈↓.

␈↓ α∧␈↓so that

␈↓ α∧␈↓␈↓ αT␈↓↓prina␈↓[(PLUS␈α
(TIMES␈αA␈α
B)␈αC),NIL]␈α
=␈α(LP␈α
PLUS␈αDOT␈α
LP␈αLP␈α
TIMES␈αDOT␈α
LP␈αA␈α
DOT
␈↓ α∧␈↓LP B DOT NIL RP RP RP DOT LP C DOT NIL RP RP RP),

␈↓ α∧␈↓i.e. ␈↓↓prina␈↓ "prints" an S-expression in "dot" notation.

␈↓ α∧␈↓On the other hand

␈↓ α∧␈↓␈↓ αT␈↓↓prinb␈↓[(PLUS (TIMES A B) C)] = (LP PLUS LP TIMES A B RP C RP),

␈↓ α∧␈↓i.e. ␈↓↓prinb␈↓ "prints" an S-expression in "list" notation.

␈↓ α∧␈↓Hint:␈αThe␈αsecond␈αargument␈αin␈αeach␈αcase␈αis␈αa␈αlist␈αof␈αthe␈αitems␈αto␈αfollow␈αthe␈α"printout"␈αof␈αthe␈αfirst
␈↓ α∧␈↓expression.  It is there to make the recursion work.

␈↓ α∧␈↓5. We have

␈↓ α∧␈↓␈↓ αT␈↓↓drop u ← ␈↓αif␈↓↓ ␈↓αn␈↓↓ u ␈↓αthen␈↓↓ ␈↓NIL␈↓↓ ␈↓αelse␈↓↓ <␈↓αa␈↓↓ u> . drop ␈↓αd␈↓↓ u␈↓.

␈↓ α∧␈↓Prove that for all lists ␈↓↓u␈↓ and ␈↓↓v␈↓

␈↓ α∧␈↓␈↓ αT␈↓↓drop[u * v] = drop u * drop v␈↓.


␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓6.␈α∞A␈α∞list␈α∞structure␈α∞is␈α
called␈α∞compact␈α∞if␈α∞EQUAL␈α∞subexpressions␈α
are␈α∞represented␈α∞by␈α∞the␈α∞same␈α
list
␈↓ α∧␈↓structure.  Thus





␈↓ α∧␈↓is a compact version of





␈↓ α∧␈↓and both represent the S-expression ((A) A).

␈↓ α∧␈↓␈↓ αT␈↓↓compact x␈↓ is a compact list structure EQUAL to ␈↓↓x.␈↓

␈↓ α∧␈↓How␈αdoes␈αthe␈αrunning␈αtime␈αof␈αyour␈α␈↓↓compact␈↓␈αdepend␈αon␈αthe␈αsize␈αof␈α␈↓↓x?␈↓␈αHow␈αfast␈αa␈αversion␈αdo␈αyou
␈↓ α∧␈↓think can be written?  How would it work?






























␈↓ α∧␈↓␈↓ ε|2␈↓ ∧